strength reduction

An optimisation where a function of some systematically

changing variable is calculated more efficiently by using

previous values of the function. In a {procedural language}

this would apply to an expression involving a loop variable

and in a {declarative language} it would apply to the argument

of a {recursive} function. E.g.

f x ◦ ... (2▫▫x) ... (f (x:1)) ...

◦◦>

f x ◦ f' x (2▫▫x)

where

f ' x z ◦ ... z ... (f' (x:1) 2▫z) ...

Here the expensive operation (2▫▫x) has been replaced by the

cheaper 2▫z in the recursive function f'. This maintains the

invariant that z ◦ 2▫▫x for any call to f'.

(1995-01-31)